import java.util.HashMap;

class LRUCache {
    int capacity;
    int size=0;
    HashMap<Integer,ListNode> map=new HashMap<>();
    LRUCache.ListNode head;
    public LRUCache(int capacity) {
        this.capacity=capacity;
    }

    public int get(int key) {
        if(map.containsKey(key)){
            LRUCache.ListNode tempNode=map.get(key);
            if(tempNode==head)
                head=head.after;
            else{
                tempNode.after.before=tempNode.before;
                tempNode.before.after=tempNode.after;

                head.before.after=tempNode;
                tempNode.before=head.before;
                head.before=tempNode;
                tempNode.after=head;
            }
            return tempNode.value;
        }
        return -1;
    }

    public void put(int key, int value) {
        LRUCache.ListNode tempNode;
        if(map.containsKey(key)){
            tempNode = map.get(key);
            tempNode.value=value;
            if(head==tempNode){
                head=head.after;
            }else {
                tempNode.after.before=tempNode.before;
                tempNode.before.after=tempNode.after;

                head.before.after=tempNode;
                tempNode.before=head.before;
                head.before=tempNode;
                tempNode.after=head;
            }

        }else{
            if(size<capacity){
                if(size==0){
                    head=new ListNode();
                    head.key=key;
                    head.value=value;
                    head.after=head;
                    head.before=head;
                    map.put(key,head);
                }else{
                    tempNode=new ListNode();
                    tempNode.key=key;
                    tempNode.value=value;

                    head.before.after=tempNode;
                    tempNode.before=head.before;
                    head.before=tempNode;
                    tempNode.after=head;

                    map.put(key,tempNode);
                }
                size++;
            }else{
                map.remove(head.key);
                tempNode=new ListNode();
                tempNode.key=key;
                tempNode.value=value;
                map.put(key,tempNode);

                if(capacity==1){
                    head=tempNode;
                    head.after=head;
                    head.before=head;
                }else {
                    tempNode.after=head.after;
                    tempNode.before=head.before;
                    head.before.after=tempNode;
                    head.after.before=tempNode;

                    head=head.after;
                }
            }
        }
    }
    class ListNode{
        int key;
        int value;
        ListNode before;
        ListNode after;
    }
}